package com.dylon.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 桶排序
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] a = new int[]{1,8,7,44,42,46,38,34,33,17,15,16,27,28,24};
        System.out.println(Arrays.toString(a));
        sort(a);
    }


    public static void sort(int[] a) {
        List[] buckets = new ArrayList[5];
        for (int i=0; i<buckets.length; i++) { //初始化
            buckets[i] = new ArrayList<Integer>();
        }
        for (int i=0; i<a.length; i++) { // 将待排序序列放入对应桶中
            int index = a[i]/10; // 对应的桶号
            buckets[index].add(a[i]);
        }
        for (int i=0;i<buckets.length;i++) { //每个桶内进行排序(使用系统自带快排)
            buckets[i].sort(null);
            for(int j=0;j<buckets[i].size();j++) { //顺便打印输出
                System.out.print(buckets[i].get(j)+" ");
            }
        }
    }

    /*
    桶排序是一种用空间换取时间的排序，桶排序重要的是它的思想，而不是具体实现，时间复杂度最好可能是线性O(n)，
    桶排序不是基于比较的排序而是一种分配式的。桶排序从字面的意思上看：
        1：若干个桶，说明此类排序将数据放入若干个桶中。
        2：每个桶有容量，桶是有一定容积的容器，所以每个桶中可能有多个元素。
        3：从整体来看，整个排序更希望桶能够更匀称，即既不溢出(太多)又不太少。
    桶排序的思想为：「将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序。」
    当然桶排序选择的方案跟具体的数据有关系，桶排序是一个比较广泛的概念，
        并且计数排序是一种特殊的桶排序，
        基数排序也是建立在桶排序的基础上。
    在数据分布均匀且每个桶元素趋近一个时间复杂度能达到O(n),但是如果数据范围较大且相对集中就不太适合使用桶排序。

     */

}
